// https://www.lintcode.com/problem/pick-carrots/

public class Solution {
    /**
     * @param carrot: an integer matrix
     * @return: Return the number of steps that can be moved.
     */
    public int PickCarrots(int[][] carrot) {
        // write your code here
        int rows = carrot.length;
        int cols = carrot[0].length;
        int cr = (rows - 1) / 2;
        int cc = (cols - 1) / 2;
        boolean[][] marked = new boolean[rows][];
        for (int i = 0; i < rows; ++i) {
            marked[i] = new boolean[cols];
            Arrays.fill(marked[i], false);
        }
        int ret = carrot[cr][cc];
        marked[cr][cc] = true;
        int r = cr;
        int c = cc;
        while (true) {
            int pos = 0;
            int[][] dirs = new int[4][];
            int[] nums = new int[]{-1, -1, -1, -1};
            dirs[0] = new int[]{r - 1, c}; // 上
            dirs[1] = new int[]{r + 1, c}; // 下
            dirs[2] = new int[]{r, c - 1}; // 左
            dirs[3] = new int[]{r, c + 1}; // 右
            for (int i = 0; i < 4; ++i) {
                int _r = dirs[i][0];
                int _c = dirs[i][1];
                if (((_r >= 0) && (_r < rows)) && ((_c >= 0) && (_c < cols)) && (!marked[_r][_c])) {
                    nums[i] = carrot[_r][_c];
                    if (nums[i] >= nums[pos]) {
                        pos = i;
                    }
                }
            }
            if (nums[pos] == -1) {
                break;
            }
            r = dirs[pos][0];
            c = dirs[pos][1];
            if (marked[r][c]) {
                break;
            }
            ret += carrot[r][c];
            marked[r][c] = true;
        }
        return ret;
    }
}